/**
 * 冒泡排序算法的三种实现
 */

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define MAX_ELEMENT 10000
#define TRUE 1
#define FALSE 0

void randArray(int a[], int n, int max);
void orderArray(int a[], int n);
void printArray(int a[], int n, int col);
void bubbleSort1(int a[], int n);
void bubbleSort2(int a[], int n);
void bubbleSort3(int a[], int n);

int main(void) {
    clock_t time_taken;

    int test_data[MAX_ELEMENT];

    randArray(test_data, MAX_ELEMENT, 10000);
    orderArray(test_data, MAX_ELEMENT);

    //printf("Before: \n");
    //printArray(test_data, MAX_ELEMENT, 20);
    time_taken = clock();
    bubbleSort1(test_data, MAX_ELEMENT);
    time_taken = clock() - time_taken;
    //printf("After: \n");
    //printArray(test_data, MAX_ELEMENT, 20);
    printf("time eslapsed: %lu colcks (%lu seconds)\n", time_taken, time_taken / CLOCKS_PER_SEC);

    randArray(test_data, MAX_ELEMENT, 10000);
    orderArray(test_data, MAX_ELEMENT);

    //printf("Before: \n");
    //printArray(test_data, MAX_ELEMENT, 20);
    time_taken = clock();
    bubbleSort2(test_data, MAX_ELEMENT);
    time_taken = clock() - time_taken;
    //printf("After: \n");
    //printArray(test_data, MAX_ELEMENT, 20);
    printf("time eslapsed: %lu colcks (%lu seconds)\n", time_taken, time_taken / CLOCKS_PER_SEC);

    randArray(test_data, MAX_ELEMENT, 10000);
    orderArray(test_data, MAX_ELEMENT);

    //printf("Before: \n");
    time_taken = clock();
    bubbleSort3(test_data, MAX_ELEMENT);
    time_taken = clock() - time_taken;
    //printf("After: \n");
    //printArray(test_data, MAX_ELEMENT, 20);
    printf("time eslapsed: %lu colcks (%lu seconds)\n", time_taken, time_taken / CLOCKS_PER_SEC);


    return 0;
}

void randArray(int a[], int n, int max) {
    srand(time(0));
    for (int i = 0; i < n; i++)
        a[i] = rand() % max;
}

void orderArray(int a[], int n) {
    for (int i = 0;  i < n; i++)
        a[i] = i;
}

void printArray(int a[], int n, int col) {
    for (int i = 0; i < n; i++) {
        printf("%6d%c", a[i], (i%col == col-1 || i == n-1)? '\n' : ' ');
    }
}

void bubbleSort1(int a[], int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n - i; j++) {
            if (a[j-1] > a[j]) {
                a[j-1] ^= a[j], a[j] ^= a[j-1], a[j-1] ^= a[j];
            }
        }
    }
}

void bubbleSort2(int a[], int n) {
    int j;
    int flag;
    flag = TRUE;
    while (flag) {
        flag = FALSE;
        for (j = 1; j < n; j++) {
            if (a[j-1] > a[j]) {
                a[j-1] ^= a[j], a[j] ^= a[j-1], a[j-1] ^= a[j];
                flag = TRUE;
            }
        }
        n--;
    }
}

void bubbleSort3(int a[], int n) {
    int j, k, flag;
    flag = n;
    while (flag > 0) {
        k = flag;
        flag = 0;
        for (j = 1; j < k; j++) {
            if (a[j-1] > a[j]) {
                a[j-1] ^= a[j], a[j] ^= a[j-1], a[j-1] ^= a[j];
                flag = j;
            }
        }
    }
}
